Hash functions are used throughout computer networks for many purposes. For example, in routing traffic between networks or through a particular network, the source and destination addresses of particular packets are utilized to determine how to route the packet. Similarly, when packets are transmitted through components of a network, such as a switch, all or part of the IP five-tuple (the source address, the destination address, the source port, the destination port and the protocol) may be used to classify the packet. Items, such as the IP five-tuple or the address of a packet, are often several bits to hundreds of bits in length. For example, the IP address is typically thirty-two bits, while the IP five-tuple is typically one hundred and four bits in length. In order to improve the time taken to perform operations using these items and thus improve the efficiency of the network, a hash function is typically used. The hash of the item is shorter than the item and can be used to identify the item. For example, a thirty-two bit address may be hashed to sixteen bits. This sixteen bit hash is then used by the network to identify the address and perform operations on the corresponding hash. Because the hash is short-hand, nickname for the item, these operations can typically be performed more rapidly, improving the efficiency of the network.
Although use of a hash improves the performance of the network, one of ordinary skill in the art will readily realize that there are problems inherent in using a hash. In particular, a hash function may map multiple items to the same hash. This phenomenon is known as a collision. When there is a collision, the item to which the hash corresponds must be capable of being uniquely determined. Typically, hash functions are not invertible. Thus, it generally cannot be determined from the hash to which of the items that collided the hash corresponds. In order to resolve the collision, therefore, the conventional network must search for original item. Such a search is time consuming and degrades performance of the network.
Furthermore, as discussed above, it may be desirable to employ a hash function on many different kinds of items having different lengths. For example, a hash for the source address for a particular packet as well as a hash for the IP five-tuple for the particular packet may be desired. In order to simplify the network, it would also be desirable for similar hash functions to be capable of providing hashes for items of different lengths.
Accordingly, what is needed is a system and method for providing a hash function which allows collisions to be more easily resolved and which can be telescoped, or expanded, so that the hash function can be used with items of different lengths. The present invention addresses such a need.